package com.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 451. 根据字符出现频率排序
 * 桶排序
 *
 * @author fy
 * @date 2022/4/7 16:48
 */
public class Solution451_1 {

    /**
     * 自己实现的桶排序
     *
     * @param s
     * @return
     */
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int maxCount = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int count = map.getOrDefault(ch, 0) + 1;
            map.put(ch, count);
            maxCount = Math.max(maxCount, count);
        }
        List<Character>[] bucket = new List[maxCount];
        for (int i = 0; i < maxCount; i++) {
            bucket[i] = new ArrayList<>();
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            bucket[entry.getValue() - 1].add(entry.getKey());
        }
        StringBuilder sb = new StringBuilder();
        for (int i = maxCount - 1; i >= 0; i--) {
            List<Character> chList = bucket[i];
            for (int j = 0; j < chList.size(); j++) {
                char ch = chList.get(j);
                for (int k = 0; k < i + 1; k++) {
                    sb.append(ch);
                }
            }
        }
        return sb.toString();
    }

    public String frequencySort1(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int maxFreq = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            int frequency = map.getOrDefault(c, 0) + 1;
            map.put(c, frequency);
            maxFreq = Math.max(maxFreq, frequency);
        }
        StringBuffer[] buckets = new StringBuffer[maxFreq + 1];
        for (int i = 0; i <= maxFreq; i++) {
            buckets[i] = new StringBuffer();
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            char c = entry.getKey();
            int frequency = entry.getValue();
            buckets[frequency].append(c);
        }
        StringBuffer sb = new StringBuffer();
        for (int i = maxFreq; i > 0; i--) {
            StringBuffer bucket = buckets[i];
            int size = bucket.length();
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < i; k++) {
                    sb.append(bucket.charAt(j));
                }
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String s = "tree";
        String res = new Solution451_1().frequencySort(s);
        System.out.println(res);
    }

}
